N-Queens Problem - Interactive Tutorial

♛ The N-Queens Challenge

The Classic Problem:

Place N queens on an NxN chessboard so no two queens attack each other.

Added Twist - Pre-Placed Queens:

Board may have K queens already placed
Verify pre-placed queens don't attack each other
Place remaining N - K queens
Queens attack: same row, column, or diagonal

Input/Output Format

Input Line 1: N (board size), K (pre-placed queens)
Next K lines: Row and column of each pre-placed queen (0-based)
Output: NxN board with 1s (queens) and 0s (empty) or "No solution found."
Constraints: 1 < N < 10, 0 ≤ K ≤ N

Example: N=4, K=1, Pre-placed at (0,1)

Pre-placed

Placed

Empty

0,00

0,1♛

0,20

0,30

0

♛

0

♛

3,30

Solution: 4 queens placed, none attacking each other

🔄 Backtracking Algorithm

Algorithm Steps

Validate: Check if pre-placed queens attack each other
Initialize: Mark pre-placed queen positions on board
Backtrack: Try placing queens row by row:
- Skip rows with pre-placed queens
- For each column, check if position is safe
- If safe, place queen and try next row
- If no column works, backtrack to previous row
Safety Check: Position (r,c) is safe if no queen in:
- Same column
- Upper-left diagonal
- Upper-right diagonal
Result: Return board if all queens placed, else "No solution found."

Key Differences from Standard N-Queens

Must validate initial configuration first
Skip rows that already have pre-placed queens
Check safety against both pre-placed and newly placed queens
May have no solution if pre-placed queens block all possibilities

Safety Check Pseudocode

function isSafe(board, row, col, n):
    // Check column
    for i from 0 to row-1:
        if board[i][col] == 1:
            return false
    
    // Check upper-left diagonal
    i = row - 1, j = col - 1
    while i >= 0 and j >= 0:
        if board[i][j] == 1:
            return false
        i--, j--
    
    // Check upper-right diagonal
    i = row - 1, j = col + 1
    while i >= 0 and j < n:
        if board[i][j] == 1:
            return false
        i--, j++
    
    return true

Time Complexity

O(N!)
Factorial - worst case tries all possibilities

Space Complexity

O(N²)
Board storage + recursion depth O(N)

🔍 Step-by-Step Queen Placement

Ready. Configure board to start demo.

N (Board size):

K (Pre-placed queens):

Pre-placed positions (row col, one per line):

Chessboard

Configure and load board

Progress Tracker

1. Parse input and create board

2. Validate pre-placed queens

3. Start backtracking from row 0

4. Try placing queens

5. Backtrack when stuck

6. Solution found or no solution

🎮 Solve Your Own N-Queens

N (Board size):

K (Pre-placed queens):

Pre-placed positions (row col, one per line):

Configure and press Solve

Test Cases

Sample 1: N=4, K=1 at (0,1)
Valid solution exists

Sample 2: N=2, K=1 at (0,0)
No solution possible

Standard: N=4, K=0
Classic 4-queens problem

📊 Algorithm Analysis

Time

O(N!)

Factorial worst case, but pruning helps

Space

O(N²)

Board storage + O(N) recursion

Why Backtracking?

Systematic: Explores all possibilities without repetition
Efficient Pruning: Abandons invalid paths early
Guaranteed: Finds solution if one exists
Natural Fit: Row-by-row placement maps to recursion

Optimization Techniques

Early Safety Checks: Test before placing, not after
Column Tracking: Use boolean array to mark occupied columns
Diagonal Tracking: Track diagonals with formula-based indexing
Heuristics: Try most constrained positions first

Pre-Placed Queens Impact

Can dramatically reduce search space (good)
May create unsolvable configurations (bad)
Need validation step before attempting to solve
Affects which rows we need to process

Real-World Applications

Resource Allocation: Non-conflicting assignment
Scheduling: Conflict-free timetabling
VLSI Design: Component placement without interference
Parallel Computing: Task distribution avoiding conflicts

♛ N-Queens Problem